package 中等;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class 打开转盘锁的最少次数 {

    public static void main(String[] args) {
        String[] deadends = {"0000"};
        String target = "8888";
        System.out.println(openLock(deadends, target));

    }

    public static int openLock(String[] deadends, String target) {
        //记录会卡死锁的组合
        HashSet<String> deads = new HashSet<>();
        for (String deadend : deadends) {
            deads.add(deadend);
        }
        if (deads.contains("0000")){
            return -1;
        }
        //防止走重复的路
        HashSet<String> visited = new HashSet<>();
        visited.add("0000");
        //记录所有下一步的集合
        Queue<String> queue = new LinkedList<>();
        queue.add("0000");
        int step = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(target)){
                    return step;
                }
                for (int j = 0; j < cur.length(); j++) {
                    String plusOne = plusOne(cur, j);
                    String minusOne = minusOne(cur, j);
                    if (!deads.contains(plusOne) && !visited.contains(plusOne)){
                        queue.add(plusOne);
                        visited.add(plusOne);
                    }
                    if (!deads.contains(minusOne) && !visited.contains(minusOne)){
                        queue.add(minusOne);
                        visited.add(minusOne);
                    }
                }
            }
            step++;
        }
        return step;
    }

    //将s[i]向上拨一下
    public static String plusOne(String s,int i){
        char[] chars = s.toCharArray();
        if (chars[i]=='9'){
            chars[i] = '0';
        }else {
            chars[i] += 1;
        }
        return new String(chars);
    }
    //将s[i]向下拨一下
    public static String minusOne(String s,int i){
        char[] chars = s.toCharArray();
        if (chars[i]=='0'){
            chars[i] = '9';
        }else {
            chars[i] -= 1;
        }
        return new String(chars);
    }

}
